{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Substring With Maximum Cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumCostSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到最大开销的子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，一个字符&nbsp;<strong>互不相同</strong>&nbsp;的字符串&nbsp;<code>chars</code>&nbsp;和一个长度与 <code>chars</code>&nbsp;相同的整数数组&nbsp;<code>vals</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>子字符串的开销</strong>&nbsp;是一个子字符串中所有字符对应价值之和。空字符串的开销是 <code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>字符的价值</strong>&nbsp;定义如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果字符不在字符串&nbsp;<code>chars</code>&nbsp;中，那么它的价值是它在字母表中的位置（下标从 <strong>1</strong>&nbsp;开始）。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>比方说，<code>'a'</code>&nbsp;的价值为&nbsp;<code>1</code>&nbsp;，<code>'b'</code>&nbsp;的价值为&nbsp;<code>2</code>&nbsp;，以此类推，<code>'z'</code>&nbsp;的价值为&nbsp;<code>26</code>&nbsp;。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>否则，如果这个字符在 <code>chars</code>&nbsp;中的位置为 <code>i</code>&nbsp;，那么它的价值就是&nbsp;<code>vals[i]</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回字符串 <code>s</code>&nbsp;的所有子字符串中的最大开销。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"adaa\", chars = \"d\", vals = [-1000]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>字符 \"a\" 和 \"d\" 的价值分别为 1 和 -1000 。\n",
    "最大开销子字符串是 \"aa\" ，它的开销为 1 + 1 = 2 。\n",
    "2 是最大开销。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"abc\", chars = \"abc\", vals = [-1,-1,-1]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>字符 \"a\" ，\"b\" 和 \"c\" 的价值分别为 -1 ，-1 和 -1 。\n",
    "最大开销子字符串是 \"\" ，它的开销为 0 。\n",
    "0 是最大开销。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "\t<li><code>1 &lt;= chars.length &lt;= 26</code></li>\n",
    "\t<li><code>chars</code>&nbsp;只包含小写英文字母，且 <strong>互不相同</strong>&nbsp;。</li>\n",
    "\t<li><code>vals.length == chars.length</code></li>\n",
    "\t<li><code>-1000 &lt;= vals[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-substring-with-maximum-cost](https://leetcode.cn/problems/find-the-substring-with-maximum-cost/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-substring-with-maximum-cost](https://leetcode.cn/problems/find-the-substring-with-maximum-cost/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"adaa\"\\n\"d\"\\n[-1000]', '\"abc\"\\n\"abc\"\\n[-1,-1,-1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        d = [i + 1 for i in range(26)]\n",
    "        for ch, v in zip(chars, vals):\n",
    "            d[ord(ch) - ord('a')] = v \n",
    "        ans = cost = i = 0\n",
    "        for j, ch in enumerate(s):\n",
    "            cost += d[ord(ch) - ord('a')] \n",
    "            while i < j and d[ord(s[i]) - ord('a')] < 0 or cost < 0:\n",
    "                cost -= d[ord(s[i]) - ord('a')]\n",
    "                i += 1\n",
    "            ans = max(ans, cost)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        m = dict(zip(chars, vals))\n",
    "        ret = f = 0\n",
    "        for c in s:\n",
    "            f =  max(f + m[c], m[c]) if c in chars else max(f + ord(c) - 96, ord(c) - 96)\n",
    "            ret = max(ret, f)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self,s:str,chars:str,vals:List[int])->int:\n",
    "        mapping = dict(zip(chars,vals))\n",
    "        f=ans=0\n",
    "        for c in s:\n",
    "            f = max(f,0)+mapping.get(c,ord(c)-ord('a')+1)\n",
    "            ans=max(ans,f)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        book = {chr(i + 97): i + 1 for i in range(26)}\n",
    "        book.update(zip(chars, vals))\n",
    "\n",
    "        minPre = pre = ans = 0\n",
    "        for cost in (book[c] for c in s):\n",
    "            pre += cost\n",
    "            if ans < (d := pre - minPre): ans = d\n",
    "            if minPre > pre: minPre = pre\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 前缀和\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        d = list(range(1, 27))\n",
    "        for i in range(len(chars)):\n",
    "            d[ord(chars[i]) - ord('a')] = vals[i]\n",
    "        pre = min_pre = ret = 0\n",
    "        for c in s:\n",
    "            pre += d[ord(c) - ord('a')]\n",
    "            ret = max(ret, pre - min_pre)\n",
    "            min_pre = min(min_pre, pre)\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        mapping = dict(zip(chars, vals))\n",
    "        ans = f = 0\n",
    "        for c in s:\n",
    "            f = max(f, 0) + mapping.get(c, ord(c) - ord('a') + 1)\n",
    "            ans = max(ans, f)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        chars = dict(zip(chars, vals))\n",
    "        ans = 0\n",
    "        min_pre_sum = pre_sum = 0\n",
    "        for i in s:\n",
    "            pre_sum += chars.get(i, ord(i)-96)\n",
    "            ans = max(ans, pre_sum-min_pre_sum)\n",
    "            min_pre_sum = min(pre_sum, min_pre_sum)\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        charDict={}\n",
    "        for x in range(26):\n",
    "            charDict[chr(ord('a')+x)]=x+1\n",
    "        for i,v in enumerate(chars):\n",
    "            charDict[v]=vals[i]\n",
    "        # print(charDict)\n",
    "        ans=0\n",
    "        pre=0\n",
    "        for c in s:\n",
    "            temp=max(charDict[c]+pre,charDict[c])\n",
    "            ans=max(ans,temp)\n",
    "            pre=temp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        #解题思路：\n",
    "        #需要确定子字符串的价值\n",
    "        #dp[i]表示以s[i]结尾的子字符串的最大价值\n",
    "        #dp[i] = max(0,dp[i - 1]) + vals[i]\n",
    "\n",
    "        n = len(s)\n",
    "        m = len(chars)\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        d = {}\n",
    "        for i in range(m):\n",
    "            d[chars[i]] = vals[i]\n",
    "        \n",
    "        chars = set(chars)\n",
    "        for i in range(26):\n",
    "            ch = chr(i + 97) \n",
    "            if ch not in chars:\n",
    "                d[ch] = i + 1\n",
    "\n",
    "        for ch in s:\n",
    "            cur = max(0,cur) + d[ch]\n",
    "            res = max(res,cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        vis={}\n",
    "        for i in range(1,27):\n",
    "            vis[i]=i\n",
    "        for c,v in zip(list(chars),vals):\n",
    "            vis[ord(c)-ord('a')+1]=v\n",
    "        print(vis)\n",
    "        Max=0\n",
    "        tmp=0\n",
    "        for t in list(s):\n",
    "            v=vis[ord(t)-ord('a')+1]\n",
    "            if v+tmp>=0:\n",
    "                tmp+=v\n",
    "                Max=max(Max,tmp)\n",
    "            else:\n",
    "                tmp=0\n",
    "        return Max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# auther yeling\n",
    "from typing import List\n",
    "from bisect import *\n",
    "from collections import *\n",
    "from functools import *\n",
    "from itertools import *\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "\n",
    "INF = 2 ** 64 - 1\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        val = [-2000] * 26\n",
    "        for i,v in enumerate(chars):\n",
    "            val[ord(v) - ord('a')] = vals[i]\n",
    "        # print(val)\n",
    "        sval = [0]*(len(s))\n",
    "        for i,v in enumerate(s):\n",
    "            if val[ord(v) - ord('a')] == -2000:\n",
    "                sval[i] = ord(v) - ord('a') + 1\n",
    "            else:\n",
    "                sval[i] = val[ord(v) - ord('a')]\n",
    "        # print(sval)\n",
    "        l = 0\n",
    "        r = 0\n",
    "        total = 0\n",
    "        ans = 0\n",
    "        while r < len(s):\n",
    "            if total >= 0:\n",
    "                total += sval[r]\n",
    "                r += 1\n",
    "            else:\n",
    "                total -= sval[l]\n",
    "                l += 1\n",
    "            ans = max(ans, total)\n",
    "            # print(l, r, ans)\n",
    "\n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "\n",
    "        def MaxSubarray(nums):\n",
    "            max_sum=cur_sum=nums[0]\n",
    "            for num in nums[1:]:\n",
    "                cur_sum=max(cur_sum+num,num)  \n",
    "                max_sum=max(max_sum,cur_sum)\n",
    "            return max_sum\n",
    "\n",
    "        char_val = {}\n",
    "        for i in range(len(chars)):\n",
    "            char_val[chars[i]]=vals[i]\n",
    "        for one in range(97,123):\n",
    "            if chr(one) in char_val:\n",
    "                continue\n",
    "            char_val[chr(one)]=one-96\n",
    "        nums = []\n",
    "        for i in s:\n",
    "            nums.append(char_val[i])\n",
    "        return max(MaxSubarray(nums),0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        ans = 0\n",
    "        arr = []\n",
    "        d = {}\n",
    "        for i, c in enumerate(list(chars)):\n",
    "            d[c] = vals[i]\n",
    "        for a in list(s):\n",
    "            if a in d:\n",
    "                arr.append(d[a])\n",
    "            else:\n",
    "                arr.append(ord(a) - ord('a') + 1)\n",
    "        cur = 0\n",
    "        for n in arr:\n",
    "            cur = max(0, n + cur)\n",
    "            ans = max(ans, cur)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        def maxCost(arr:list):\n",
    "            n = len(arr)\n",
    "            cur_sum = 0\n",
    "            max_sum = 0\n",
    "            for num in arr:\n",
    "                cur_sum = max(num, cur_sum+num)\n",
    "                max_sum = max(max_sum, cur_sum)\n",
    "            return max(0, max_sum)\n",
    "        \n",
    "        chars = {c:i for i,c in enumerate(chars)}\n",
    "        costs = []\n",
    "        for c in s:\n",
    "            if c not in chars:\n",
    "                cost = ord(c)-ord('a') + 1\n",
    "            else:\n",
    "                cost = vals[chars[c]]\n",
    "            costs.append(cost)\n",
    "        \n",
    "        return maxCost(costs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        table = dict(zip(chars, vals))\n",
    "        l = []\n",
    "        for c in s:\n",
    "            if c in table:\n",
    "                l.append(table[c])\n",
    "            else:\n",
    "                l.append(ord(c) - 96)\n",
    "        # 扫描法\n",
    "        sum_ = ans = 0\n",
    "        for i in l:\n",
    "            if sum_ < 0:\n",
    "                sum_ = i\n",
    "            else:\n",
    "                sum_ += i\n",
    "            ans = max(ans, sum_)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        book = {chr(i + 97): i + 1 for i in range(26)}\n",
    "        book.update(dict(zip(chars, vals)))\n",
    "        costs = [book[c] for c in s]\n",
    "\n",
    "        minPre = pre = ans = 0\n",
    "        for cost in costs:\n",
    "            pre += cost\n",
    "            if ans < (d := pre - minPre): ans = d\n",
    "            if minPre > pre: minPre = pre\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        book = {chr(i + 97): i + 1 for i in range(26)}\n",
    "        book.update(dict(zip(chars, vals)))\n",
    "        costs = [book[c] for c in s]\n",
    "\n",
    "        minPre = pre = ans = 0\n",
    "        for cost in costs:\n",
    "            pre += cost\n",
    "            if ans < (d := pre - minPre): ans = d\n",
    "            if minPre > pre: minPre = pre\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        book = {chr(i + 97): i + 1 for i in range(26)}\n",
    "        book.update(dict(zip(chars, vals)))\n",
    "        costs = [book[c] for c in s]\n",
    "\n",
    "        minPre = pre = ans = 0\n",
    "        for cost in costs:\n",
    "            pre += cost\n",
    "            ans = max(ans, pre - minPre)\n",
    "            minPre = min(minPre, pre)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        book = {chr(i + 97): i + 1 for i in range(26)}\n",
    "        book.update(zip(chars, vals))\n",
    "        costs = [book[c] for c in s]\n",
    "\n",
    "        minPre = pre = ans = 0\n",
    "        for cost in costs:\n",
    "            pre += cost\n",
    "            if ans < (d := pre - minPre): ans = d\n",
    "            if minPre > pre: minPre = pre\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, st: str, chars: str, vals: List[int]) -> int:\n",
    "        map = {}\n",
    "        for k, v in zip(chars, vals):\n",
    "            map[k] = v\n",
    "        for i in range(26):\n",
    "            s = chr(ord('a') + i)\n",
    "            if s in map: continue\n",
    "            map[s] = i + 1\n",
    "        \n",
    "        @lru_cache(maxsize=3)\n",
    "        def dp(i):\n",
    "            if i < 0: return 0\n",
    "            return max(\n",
    "                map[st[i]],\n",
    "                dp(i - 1) + map[st[i]]\n",
    "            )\n",
    "\n",
    "        return max(0, max(dp(i) for i in range(len(st))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        dic = dict(zip(chars, vals))\n",
    "        s = list(s)\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] in chars:\n",
    "                s[i] = dic[s[i]]\n",
    "            else:\n",
    "                s[i] = ord(s[i]) - 96\n",
    "        \n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            cur += s[i]\n",
    "            ans = max(ans, cur)\n",
    "            if cur < 0:\n",
    "                cur = 0\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        nums = [0] * n \n",
    "        cnt = defaultdict()\n",
    "        for c, v in zip(chars, vals):\n",
    "            cnt[c] = v\n",
    "        for i, c in enumerate(s):\n",
    "            if c in cnt.keys():\n",
    "                nums[i] = cnt[c]\n",
    "            else:\n",
    "                nums[i] = ord(c) - ord('a') + 1\n",
    "        mx = nums[0]\n",
    "        ans = max(mx, 0)\n",
    "        for i in range(1, n):\n",
    "            mx = max(mx + nums[i], nums[i])\n",
    "            ans = max(ans, mx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        \n",
    "        x = Counter()\n",
    "        val_size = len(vals)\n",
    "        for i in range(val_size):\n",
    "            x[chars[i]] = vals[i]\n",
    "        for i in range (97,123):\n",
    "            if chr(i) not in chars:\n",
    "               x[chr(i)] = i - 96\n",
    "        ans = 0\n",
    "        result = []\n",
    "        pos = 0\n",
    "        cnt = 0\n",
    "        flag = 0\n",
    "        for i in s:\n",
    "            if x[i] >= 0:\n",
    "                if flag:\n",
    "                     result.append(cnt)\n",
    "                     cnt = 0\n",
    "                ans += x[i]\n",
    "                flag = 0\n",
    "            else:\n",
    "                result.append(ans)\n",
    "                ans = 0\n",
    "                flag = 1 \n",
    "                cnt += x[i]\n",
    "        if ans != 0:\n",
    "            result.append(ans)\n",
    "        if cnt != 0:\n",
    "            result.append(cnt)\n",
    "        print(result)\n",
    "        w = len(result)\n",
    "        if w == 1:\n",
    "            return max(0,result[0])\n",
    "        if w == 2:\n",
    "            p = max(result[0],result[1])\n",
    "            p =max(result[0] + result[1], p)\n",
    "            return max(p, 0)\n",
    "        ans = 0\n",
    "        f = 0\n",
    "        for i in result:\n",
    "            f = max(f,0) + i\n",
    "            ans = max(ans,f)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, st: str, chars: str, vals: List[int]) -> int:\n",
    "        map = {}\n",
    "        for k, v in zip(chars, vals):\n",
    "            map[k] = v\n",
    "        for i in range(26):\n",
    "            s = chr(ord('a') + i)\n",
    "            if s in map: continue\n",
    "            map[s] = i + 1\n",
    "        \n",
    "        @lru_cache\n",
    "        def dp(i):\n",
    "            if i < 0: return 0\n",
    "            return max(\n",
    "                map[st[i]],\n",
    "                dp(i - 1) + map[st[i]]\n",
    "            )\n",
    "\n",
    "        return max(0, max(dp(i) for i in range(len(st))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "\n",
    "        chars_value_dict = {ch : val for ch , val in zip(chars, vals)}\n",
    "        print(chars_value_dict)\n",
    "        ss = []\n",
    "        for ch in s:\n",
    "            if ch in chars_value_dict:\n",
    "                ss.append(chars_value_dict[ch])\n",
    "            else:\n",
    "                ss.append(ord(ch) - ord('a') + 1)\n",
    "        print(ss)\n",
    "\n",
    "        max_value = 0\n",
    "        total_sum = 0\n",
    "        for ii in range(len(ss)):\n",
    "            total_sum += ss[ii]\n",
    "            max_value = max(max_value, total_sum)\n",
    "            total_sum = max(total_sum, 0)\n",
    "\n",
    "    \n",
    "        return max_value\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in range(len(chars)):\n",
    "            dic[chars[i]] = vals[i]\n",
    "        array = []\n",
    "        for i in s:\n",
    "            if i in dic:\n",
    "                array.append(dic[i])\n",
    "            else:\n",
    "                array.append(ord(i) - ord('a') + 1)\n",
    "        print(array)\n",
    "        global_max = -inf\n",
    "        local_max = 0\n",
    "        for i in range(len(array)):\n",
    "            local_max += array[i]\n",
    "            local_max = max(0, local_max)\n",
    "            global_max = max(global_max, local_max)\n",
    "        return global_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in range(26):\n",
    "            c = chr(ord('a') + i)\n",
    "            if c in chars:\n",
    "                dic[c] = vals[chars.find(c)]\n",
    "            else:\n",
    "                dic[c] = i + 1\n",
    "        stack = deque([0])\n",
    "        cur = 0\n",
    "        res = 0\n",
    "        for c in s:\n",
    "            cur += dic[c]\n",
    "            while stack and stack[-1] >= cur:\n",
    "                stack.pop()\n",
    "            stack.append(cur)\n",
    "            if stack:\n",
    "                res = max(cur - stack[0], res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mp = {}\n",
    "        for i in range(26):\n",
    "            x = chr(ord('a') + i)\n",
    "            if x in chars:\n",
    "                j = chars.index(x)\n",
    "                mp[x] = vals[j]\n",
    "            else:\n",
    "                mp[x] = i + 1\n",
    "        n = len(s)\n",
    "        f = [0] * n\n",
    "        for i in range(n):\n",
    "            f[i] = max(f[i], mp[s[i]] + (f[i - 1] if f[i - 1] > 0 else 0))\n",
    "            ans = max(ans, f[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        dp = [0] * (len(s)+1)\n",
    "        values = defaultdict()\n",
    "        for i in range(1,27):\n",
    "            values[chr(i+96)] = i\n",
    "        for i in range(len(chars)):\n",
    "            values[chars[i]] = vals[i]\n",
    "        for i in range(1,len(dp)):\n",
    "            if dp[i-1] < 0:\n",
    "                dp[i] = values[s[i-1]]\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + values[s[i-1]]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        mp = {}\n",
    "        for i in range(26):\n",
    "            c = chr(i + 97)\n",
    "            mp[c] = i + 1\n",
    "        for i in range(len(chars)):\n",
    "            mp[chars[i]] = vals[i]\n",
    "\n",
    "        n = len(s)\n",
    "        f = [0] * n\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            v = mp[s[i]]\n",
    "            f[i] = max(f[i - 1] + v, 0)\n",
    "            res = max(res, f[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        status = [0] * n\n",
    "\n",
    "        dic = {}\n",
    "        v = 0\n",
    "        for i in range(len(chars)):\n",
    "            dic[chars[i]] = i\n",
    "        dic2 = {}\n",
    "\n",
    "         \n",
    "        for i in range(0, n):\n",
    "            if s[i] in dic.keys():\n",
    "                t = vals[dic[s[i]]]\n",
    "            else:\n",
    "                t = ord(s[i]) - 96\n",
    "\n",
    "            if 0 == i:\n",
    "                status[i] = t\n",
    "            else:\n",
    "                status[i] = max(t, t + status[i - 1])\n",
    "            #print(status[i])\n",
    "            v = max(v, status[i])\n",
    "        return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        mapping = dict(zip(chars, vals))\n",
    "        dp = [None] * len(s)\n",
    "        dp[0] = mapping.get(s[0], ord(s[0])-ord('a')+1)\n",
    "        for i in range(1, len(s)):\n",
    "            val = mapping.get(s[i], ord(s[i])-ord('a')+1)\n",
    "            dp[i] = max(dp[i-1] + val, val)\n",
    "        return max(max(dp), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        dic = {}\n",
    "        for i, ch in enumerate(chars):\n",
    "            dic[ch] = vals[i]\n",
    "        for i in range(26):\n",
    "            ch = chr(ord('a') + i)\n",
    "            if ch not in dic:\n",
    "                dic[ch] = i + 1\n",
    "        \n",
    "        ans = 0\n",
    "        \n",
    "        nums = [dic[ch] for ch in s]\n",
    "        \n",
    "        def maxSubArray(nums: List[int]) -> int:\n",
    "            n = len(nums)\n",
    "\n",
    "            for i in range(1, n):\n",
    "                nums[i] = max(nums[i], nums[i] + nums[i - 1])\n",
    "\n",
    "            return max(nums)\n",
    "        \n",
    "        ans = max(maxSubArray(nums), 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        value=[x+1 for x in range(26)]\n",
    "        for i in range(len(chars)):\n",
    "            tmp=ord(chars[i])-ord('a')\n",
    "            value[tmp]=vals[i]\n",
    "        numval=[]\n",
    "        ans=0\n",
    "        left=0\n",
    "        for c in s:\n",
    "            tmp=ord(c)-ord('a')\n",
    "            ll=len(numval)\n",
    "            if ll==0:\n",
    "                numval.append(value[tmp])\n",
    "            else:\n",
    "                numval.append(max(numval[ll-1]+value[tmp],value[tmp]))\n",
    "            \n",
    "        ans=max(ans,max(numval))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        chars = [i for i in chars]\n",
    "        c = [i for i in \"abcdefghijklmnopqrstuvwxyz\"]\n",
    "        v = {i: x+1 for x,i in enumerate(c)}\n",
    "        c_v = {}\n",
    "        for i in zip(chars, vals):\n",
    "            c_v[i[0]] = i[1]\n",
    "        vs = [0]\n",
    "        for i in s:\n",
    "            if i in chars:\n",
    "                \n",
    "                vs.append(c_v[i] + vs[-1])\n",
    "                continue\n",
    "            vs.append(v[i] + vs[-1])\n",
    "        stick = 0\n",
    "        max_ = 0\n",
    "        \n",
    "        for i in range(1, len(vs)):\n",
    "            if vs[i] - vs[stick] > max_:\n",
    "                max_ = vs[i] - vs[stick]\n",
    "            elif vs[i] - vs[stick] <= 0:\n",
    "                stick = i\n",
    "        \n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        h = dict(zip(chars, vals))\n",
    "        for i in range(1, 27):\n",
    "            c = chr(i + ord('a') - 1)\n",
    "            if c not in h.keys():\n",
    "                h[c] = i\n",
    "        \n",
    "        f = [max(0, h[s[i]]) for i in range(len(s))]\n",
    "    \n",
    "        for i in range(1, len(s)):\n",
    "            c = s[i]\n",
    "            f[i] = max(f[i - 1] + h[c], h[c])\n",
    "  \n",
    "        return max(f)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        d = {}\n",
    "        for i in range(len(chars)):\n",
    "            d[chars[i]] = vals[i]\n",
    "        for i, ch in enumerate('abcdefghijklmnopqrstuvwxyz'):\n",
    "            if ch not in d:\n",
    "                d[ch] = i+1\n",
    "        n = len(s)\n",
    "        sm = [0] * (n + 1)\n",
    "        minv, ans = 0, 0\n",
    "        for i in range(n):\n",
    "            sm[i + 1] = sm[i] + d[s[i]]\n",
    "            ans = max(ans, sm[i + 1] - minv)\n",
    "            minv = min(minv, sm[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        # 各字母的价值\n",
    "        value = {chr(ord('a') + i): i + 1 for i in range(26)}\n",
    "        for i, ch in enumerate(chars):\n",
    "            value[ch] = vals[i]\n",
    "\n",
    "        n = len(s)\n",
    "        prefix = [0] * (n + 1)  # prefix[i]: s[:i]的价值\n",
    "        for i, ch in enumerate(s):\n",
    "            prefix[i + 1] = prefix[i] + value[ch]\n",
    "\n",
    "        ans = mini = 0  # mini: 已遍历prefix的最小值\n",
    "        for i in range(n):\n",
    "            ans = max(ans, prefix[i + 1] - mini)\n",
    "            mini = min(mini, prefix[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        prefix = [0] * (n + 1)\n",
    "        d = {chars[i]: vals[i] for i in range(len(chars))}\n",
    "        for i in range(n):\n",
    "            if s[i] in d:\n",
    "                prefix[i + 1] = prefix[i] + d[s[i]]\n",
    "            else:\n",
    "                prefix[i + 1] = prefix[i] + ord(s[i]) - ord('a') + 1\n",
    "        ans = 0\n",
    "        now_min = 0\n",
    "        for i in range(1, n + 1):\n",
    "            ans = max(ans, prefix[i] - now_min)\n",
    "            now_min = min(now_min, prefix[i])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        l = [0] * n\n",
    "        for i in range(n):\n",
    "            if s[i] in chars:\n",
    "                l[i] = vals[chars.index(s[i])]\n",
    "            else:\n",
    "                l[i] = ord(s[i]) - ord('a') + 1\n",
    "        dp = [0] * (1+n)\n",
    "        for i in range(n):\n",
    "            dp[i+1] = max(dp[i]+l[i],l[i])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        dct = dict(zip(\"abcdefghijklmnopqrstuvwxyz\" + chars, list(range(1, 27)) + vals))\n",
    "        l, r, ans, lens, lst = 0, 0, 0, len(s), list(accumulate([dct[c] for c in s], initial=0))\n",
    "\n",
    "        while True:\n",
    "            # 对前缀和数组求差值\n",
    "            if lst[r] >= lst[l]:\n",
    "                r += 1\n",
    "                if r <= lens:\n",
    "                    ans = max(ans, lst[r] - lst[l])\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                l = r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        dict_ord = {chr(i): i-96 for i in range(ord('a'),ord('z')+1)}\n",
    "        dict_val = dict(zip(chars, vals))\n",
    "        # print(dict_ord)\n",
    "        # print(dict_val)\n",
    "\n",
    "        def get_value(x):\n",
    "            if x in chars:\n",
    "                return dict_val[x]\n",
    "            return dict_ord[x]\n",
    "            \n",
    "        n = len(s)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        dp = [0] * n\n",
    "        dp[0] = max(get_value(s[0]), 0)\n",
    "        for i in range(1, n):\n",
    "            dp[i] = max(dp[i-1],0) + get_value(s[i])\n",
    "        # print(dp)\n",
    "        return max(dp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        cnt = []\n",
    "        for i,st in enumerate(s):\n",
    "            if st in chars:\n",
    "                for i, ch in enumerate(chars):\n",
    "                    if ch == st:\n",
    "                        cnt.append(vals[i])\n",
    "                        break\n",
    "            else:\n",
    "                cnt.append(ord(st) - ord('a') + 1)\n",
    "        # dp = [[0] * 2 for _ in range(len(cnt))]\n",
    "        # dp[0][0], dp[0][1] = 0, \n",
    "        # for i in range(1,len(cnt)):\n",
    "        #     for j in range(i, len(cnt)):\n",
    "        #         dp[i][j] = \n",
    "        dp = [0] * len(cnt)\n",
    "        dp[0] = cnt[0]\n",
    "        for i in range(1, len(cnt)):\n",
    "            dp[i] = max(dp[i - 1] + cnt[i], cnt[i])\n",
    "        return max(max(dp), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        n=len(s)\n",
    "        dp=[0]*n\n",
    "        ords=[1]*26\n",
    "        for i in range(26):\n",
    "            ords[i]=i+1\n",
    "        def getord(ch):\n",
    "            return ord(ch)-ord(\"a\")\n",
    "        for i,ch in enumerate(chars):\n",
    "            ords[getord(ch)]=vals[i]\n",
    "        #print(ords)\n",
    "        dp[0]=ords[getord(s[0])]\n",
    "        for i in range(1,n):\n",
    "            dp[i]=ords[getord(s[i])]\n",
    "            #print(dp[i],dp[i-1])\n",
    "            if dp[i-1]>0:\n",
    "                dp[i]+=dp[i-1]\n",
    "        #print(dp)\n",
    "        return max(0,max(dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        dic={chars[i]:vals[i] for i in range(len(chars))}\n",
    "        n=len(s)\n",
    "        dp=[0]*(n+1)\n",
    "        ans=-inf\n",
    "        for i in range(1,n+1):\n",
    "            dp[i]=max(dic.get(s[i-1],ord(s[i-1])-ord('a')+1),dic.get(s[i-1],ord(s[i-1])-ord('a')+1)+dp[i-1],0)\n",
    "            ans=max(ans,dp[i])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        aaa={}\n",
    "        for i,c in enumerate(chars):\n",
    "            aaa[c]=vals[i]\n",
    "        def char_to_value(char):\n",
    "            return ord(char) - ord('a') + 1\n",
    "        #@cache\n",
    "        #def dfs(i):\n",
    "        #    if i<0:\n",
    "        #        return 0\n",
    "        #    if s[i] in aaa: val=aaa[s[i]]\n",
    "        #    else:val=char_to_value(s[i])\n",
    "        #    return max(dfs(i-1)+val,val)\n",
    "        #ans=0\n",
    "        #for i in range(len(s)):\n",
    "        #    ans=max(ans,dfs(i))\n",
    "        #return ans\n",
    "        n=len(s)\n",
    "        f=[0]*(n+1)\n",
    "        for i,x in enumerate(s):\n",
    "            if x in aaa:val=aaa[x]\n",
    "            else:val=char_to_value(x)\n",
    "            f[i+1]=max(f[i]+val,val)\n",
    "        return max(f)\n",
    "        #pre=ans=0\n",
    "        #for i,x in enumerate(s):\n",
    "        #    if x in aaa:val=aaa[x]\n",
    "        #    else:val=char_to_value(x)\n",
    "        #    pre=max(pre,pre+val)\n",
    "        #    ans=max(ans,pre)\n",
    "        #return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        f = {}\n",
    "        for i, x in enumerate(\"abcdefghijklmnopqrstuvwxyz\"):\n",
    "            f[x] = i + 1\n",
    "        for [i, x] in zip(chars, vals):\n",
    "            f[i] = x\n",
    "        dp = [0] * len(s)\n",
    "        for i, x in enumerate(s):\n",
    "            dp[i] = max(dp[i - 1] + f[x], f[x])\n",
    "            if dp[i] < 0:\n",
    "                dp[i] = 0\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        mp = {}\n",
    "        \n",
    "        for i in range(1, 27):\n",
    "            mp[chr(97 + i - 1)] = i\n",
    "\n",
    "        \n",
    "        for a, b in zip(chars, vals):\n",
    "            mp[a] = b\n",
    "\n",
    "        dp = [0] * len(s)\n",
    "        dp[0] = mp[s[0]]\n",
    "        res = max(res, dp[0])\n",
    "        for i in range(1, len(dp)):\n",
    "            if dp[i - 1] >= 0:\n",
    "                dp[i] = dp[i - 1] + mp[s[i]]\n",
    "            else:\n",
    "                dp[i] = mp[s[i]]\n",
    "\n",
    "            res = max(res, dp[i])\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        dp = [0] * len(s)\n",
    "        m = dict()\n",
    "        # init\n",
    "        for i, v in enumerate(\"abcdefghijklmnopqrstuvwxyz\"):\n",
    "            m[v] = i+1\n",
    "        for i, c in enumerate(chars):\n",
    "            m[c] = vals[i]\n",
    "        res = max(0, m.get(s[0]))\n",
    "        dp[0] = res\n",
    "        i, length = 1, len(s)\n",
    "        while i < length:\n",
    "            dp[i] = max(dp[i-1] + m.get(s[i]), m.get(s[i]))\n",
    "            res = max(res, dp[i])\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        mapping = {}\n",
    "        for asc in range(97, 123):\n",
    "            mapping[chr(asc)] = asc - 96\n",
    "        for i, ch in enumerate(chars):\n",
    "            mapping[ch] = vals[i]\n",
    "        \n",
    "        n = len(s)\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = max(dp[i-1], 0) + mapping[s[i-1]]\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        value = {chars[i]: vals[i] for i in range(len(chars))}\n",
    "        interval_value = [0]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in value:\n",
    "                temp = value[s[i]]\n",
    "            else:\n",
    "                temp = ord(s[i]) - ord('a') + 1\n",
    "            if len(interval_value) > 1 and interval_value[-1] >= 0:\n",
    "                interval_value.append(interval_value[-1] + temp)\n",
    "            else:\n",
    "                interval_value.append(temp) \n",
    "        return max(interval_value)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        # 各字母映射为其价值\n",
    "        value = {ch: vals[i] for i, ch in enumerate(chars)}\n",
    "        s = [value.get(ch, ord(ch) - ord('a') + 1) for ch in s]\n",
    "\n",
    "        n = len(s)\n",
    "        prefix = [0] + list(accumulate(s))  # prefix[i]: s[:i]的价值\n",
    "        ans = mini = 0  # mini: 已遍历prefix的最小值\n",
    "        for i in range(n):\n",
    "            ans = max(ans, prefix[i + 1] - mini)\n",
    "            mini = min(mini, prefix[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        dp = [0 for _ in range(len(s))]\n",
    "        map = [i+1 for i in range(26)]\n",
    "        for i in range(len(chars)):\n",
    "            map[ord(chars[i]) - ord('a')] = vals[i]\n",
    "        dp[0] = map[ord(s[0]) - ord('a')]\n",
    "        for i in range(1, len(s)):\n",
    "            dp[i] = max(dp[i-1] + map[ord(s[i]) - ord('a')], map[ord(s[i]) - ord('a')])\n",
    "        return max(dp + [0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        n= len(s)\n",
    "        ans = 0\n",
    "        pre_sum = [0]*(n+1)\n",
    "        for i in range(len(chars)):\n",
    "            d[chars[i]]=vals[i]\n",
    "        min_pre = 0\n",
    "        for i in range(1,n+1):\n",
    "            if s[i-1] in chars:\n",
    "                pre_sum[i]=pre_sum[i-1]+d[s[i-1]]\n",
    "            else:\n",
    "                pre_sum[i]=pre_sum[i-1]+ord(s[i-1])-ord('a')+1\n",
    "            ans = max(ans,pre_sum[i]-min_pre)\n",
    "            min_pre = min(min_pre,pre_sum[i])\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        val_dict = {}\n",
    "        for i in range(ord('a'), ord('z') + 1):\n",
    "            val_dict[chr(i)] = i - 96\n",
    "        for i in range(len(chars)):\n",
    "            val_dict[chars[i]] = vals[i]\n",
    "        svals = []\n",
    "        for i in s:\n",
    "            svals.append(val_dict[i])\n",
    "        max_list, tem = [], 0\n",
    "        for i in range(len(s)):\n",
    "            if tem + svals[i] < 0:\n",
    "                max_list.append(tem)\n",
    "                tem = 0\n",
    "            else:\n",
    "                tem += svals[i]\n",
    "                max_list.append(tem)\n",
    "        return max(max_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        cost = list(range(1, 27))\n",
    "        for i, c in enumerate(chars):\n",
    "            cost[ord(c) -ord('a')] = vals[i]\n",
    "        arr = [cost[ord(c)-ord('a')] for c in s]\n",
    "        # print(arr)\n",
    "        dp = [-inf]*len(arr)\n",
    "        dp[0] = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            dp[i] = max(arr[i], arr[i] + dp[i-1])\n",
    "        ans = max(dp)\n",
    "        return max(0, ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        dic = {chr(i):i-96 for i in range(97,97+26)}\n",
    "        for i in range(len(chars)):\n",
    "            dic[chars[i]] = vals[i]\n",
    "        dp = [-float('inf') for i in range(len(s))]\n",
    "        dp[0] = dic[s[0]]\n",
    "        for i in range(1,len(s)):\n",
    "            dp[i] = max(dic[s[i]],dic[s[i]]+dp[i-1]) \n",
    "        return max(dp+[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        _s=[]\n",
    "        for w in s:\n",
    "            if w in chars:\n",
    "                v = vals[chars.index(w)]\n",
    "            else:\n",
    "                v = ord(w) - 96\n",
    "            _s.append(v)\n",
    "        \n",
    "        dps =[]\n",
    "        def get_dp(i):\n",
    "            if i==0:\n",
    "                dpi = _s[0]\n",
    "            else:\n",
    "                _dp = dps[i-1]\n",
    "                if _dp<0:\n",
    "                    dpi = _s[i]\n",
    "                else:\n",
    "                    dpi = _dp+_s[i]\n",
    "            dps.append(dpi)\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            get_dp(i)\n",
    "        _max = max(dps)\n",
    "        if _max<0:\n",
    "            return 0\n",
    "        else:\n",
    "            return _max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        pre_sum = [0]\n",
    "        cs = dict(zip(chars, vals))\n",
    "        # print(cs)\n",
    "        for i in range(n):\n",
    "            if s[i] in cs:\n",
    "                pre_sum.append(pre_sum[-1] + cs[s[i]])\n",
    "            else:\n",
    "                pre_sum.append(pre_sum[-1] + ord(s[i]) - ord(\"a\") + 1)\n",
    "        # print(pre_sum)\n",
    "        min_val = 0\n",
    "        res = 0\n",
    "        for p in pre_sum[1:]:\n",
    "            res = max(res, p - min_val)\n",
    "            min_val = min(p, min_val)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
